Continued fraction
In mathematics, a continued fraction is an expression such as : x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots\,}}}} where a''0 is some integer and all the other numbers ''an'' are ''positive integers. Longer expressions are defined analogously. If the partial numerators and partial denominators are allowed to assume arbitrary values, which may in some contexts include functions, the resulting expression is a generalized continued fraction. When it is necessary to distinguish the standard form above from generalized continued fractions, it may be called a simple or regular continued fraction, or is said to be in canonical form. Motivation The study of continued fractions is motivated by a desire to have a "mathematically pure" representation for the real numbers. For calendars, the continued fraction can show the structure of an intercalation cycle, where the intercalary years are as evenly spaced as possible. Most people are familiar with the decimal representation of real numbers: : r = \sum_{i=0}^\infty a_i 10^{-i} = a_0 + a_1/10 + a_2/100 + a_3/1000 + \cdots where a''0 may be any integer, and each ''ai'' is an element of {0, 1, 2, ..., 9}. In this representation, the number π, for example, is represented by the sequence of integers {3, 1, 4, 1, 5, 9, 2, ...}. This representation has some problems, however. One problem is the appearance of the arbitrary constant 10 in the formula above. Why 10? This is because of a biological accident, not because of anything related to mathematics. 10 is used because it is the standard base of our number system (10 fingers); we may just as well use base 8 (octal) or base 2 (binary). Another problem is that many rational numbers lack finite representations in this system. For example, the number 1/3 is represented by the infinite sequence {0, 3, 3, 3, 3, ....}. Continued fraction notation is a representation for the real numbers that avoids both these problems. Let us consider how we might describe a number like 415/93, which is around 4.4624. This is approximately 4. Actually it is a little bit more than 4, about 4 + 1/2. But the 2 in the denominator is not correct; the correct denominator is a little bit ''more than 2, about 2 + 1/6, so 415/93 is approximately 4 + 1/(2 + 1/6). But the 6 in the denominator is not correct; the correct denominator is a little bit more than 6, actually 6+1/7. So 415/93 is actually 4+1/(2+1/(6+1/7)). This is exact. Dropping the redundant parts of the expression 4+1/(2+1/(6+1/7)) gives the abbreviated notation 2, 6, 7. The continued fraction representation of real numbers can be defined in this way. It has several desirable properties: * The continued fraction representation for a number is finite if and only if the number is rational. * Continued fraction representations for "simple" rational numbers are short. * The continued fraction representation of any rational number is unique if it has no trailing 1. (For any rational number expressed as a continued fraction a,...,z with z>1 there is a less efficient representation ending in 1, N;a,...,z-1,1). * The continued fraction representation of an irrational number is unique. * The terms of a continued fraction will repeat if and only if it is the continued fraction representation of a quadratic irrational, that is, a real solution to a quadratic equation with integer coefficients http://mathworld.wolfram.com/PeriodicContinuedFraction.html. * Truncating the continued fraction representation of a number x'' early yields a rational approximation for ''x which is in a certain sense the "best possible" rational approximation (see theorem 5, corollary 1 below for a formal statement). This last property is extremely important, and is not true of the conventional decimal representation. Truncating the decimal representation of a number yields a rational approximation of that number, but not usually a very good approximation. For example, truncating 1/7 = 0.142857... at various places yields approximations such as 142/1000, 14/100, and 1/10. But clearly the best rational approximation is "1/7" itself. Truncating the decimal representation of π yields approximations such as 31415/10000 and 314/100. The continued fraction representation of π begins 7, 15, 1, 292, .... Truncating this representation yields the excellent rational approximations 3, 22/7, 333/106, 355/113, 103993/33102, ... The denominators of 314/100 and 333/106 are almost the same, but the error in the approximation 314/100 is nineteen times as large as the error in 333/106. As an approximation to π, 7, 15, 1 is more than one hundred times more accurate than 3.1416. Calculating continued fraction representations Consider a real number r''. Let ''i be the integer part and f'' the fractional part of ''r. Then the continued fraction representation of r'' is [''i; …], where "…" is the continued fraction representation of 1/''f''. It is customary to replace the first comma by a semicolon. To calculate a continued fraction representation of a number r'', write down the integer part of ''r. Subtract this integer part from r''. If the difference is 0, stop; otherwise find the reciprocal of the difference and repeat. The procedure will halt if and only if ''r was rational. The number 3.245 can also be represented by the continued fraction expansion 4, 12, 3, 1; refer to Finite continued fractions below. This algorithm is suitable for real numbers, but can lead to numerical disaster if implemented with floating point numbers. Instead, any floating point number is an exact rational (the denominator is usually a power of two on modern computers, and a power of ten on electronic calculators), so a variant of Euclid's GCD algorithm can be used to give exact results. Use in Calendars The continued fractions can be used in calendars to create intercalation cycles. See lunisolar calendar for years in months, lunar calendar for months in days. History of continued fractions * 300 BC Euclid, Elements - Algorithm for greatest common divisor which generates a continued fraction as a by-product * 1579 Rafael Bombelli, L'Algebra Opera - method for the extraction of square roots which is related to continued fractions * 1613 Pietro Cataldi, Trattato del modo brevissimo di trovar la radice quadra delli numeri - first notation for continued fractions :Cataldi represented a continued fraction as a_0.\, & n_1 \over d_1. & n_2 \over d_2. & {n_3 \over d_3} with the dots indicating where the following fractions went. * 1695 John Wallis, Opera Mathematica - introduction of the term "continued fraction" * ca 1780 Joseph Louis Lagrange - provided the general solution to Pell's equation using continued fractions similar to Bombelli's * 1748 Leonhard Euler, Introductio in analysin infinitorum. Vol. I, Chapter 18 - proved the equivalence of a certain form of continued fraction and a generalized infinite series * 1813 Karl Friedrich Gauss, Werke, Vol. 3, pp. 134-138 - derived a very general complex-valued continued fraction via a clever identity involving the hypergeometric series External links *Online continued fraction calculator *Francois Balsalobre cfc - a (cli) continued fraction calculator for POSIX and Cygwin *The Antikythera Mechanism I: Gear ratios and continued fractions *Calendar and continued fractions by Yury Grabovsky *Real Numbers and Fascinating Fractions by Rainer Radok *The Golden Ratio and The Fibonacci Numbers, with a use of continued fractions in calendrical calculations as an example *This subject in Wikipedia: References *A. Ya. Khinchin, Continued Fractions, , English translation University of Chicago Press, ISBN 0-486-69630-8 * , Die Lehre von den Kettenbrüchen, Chelsea Publishing Company, New York, NY . *Andrew M. Rockett and Peter Szusz, Continued Fractions, World Scientific Press, ISBN 978-9-81-021052-6 *H. S. Wall, Analytic Theory of Continued Fractions, D. Van Nostrand Company, Inc., ISBN 0-8284-0207-8 Category:Mathematical constructs Category:Applied mathematics